package simple.number;

/**
 * <a href="https://leetcode.cn/problems/count-largest-group/">1399. 统计最大组的数目</a>
 * 给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。
 * 请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。
 * 示例 1：
 *   输入：n = 13
 *   输出：4
 *   解释：总共有 9 个组，将 1 到 13 按数位求和后这些组分别是：
 *     [1,10]，[2,11]，[3,12]，[4,13]，[5]，[6]，[7]，[8]，[9]。总共有 4 个组拥有的数字并列最多。
 * 示例 2：
 *   输入：n = 2
 *   输出：2
 *   解释：总共有 2 个大小为 1 的组 [1]，[2]。
 * 示例 3：
 *   输入：n = 15
 *   输出：6
 * 示例 4：
 *   输入：n = 24
 *   输出：5
 * 提示：
 *   1 <= n <= 10^4
 * @author 刘学松
 * @date 2023-08-04 16:49
 */
public class 统计最大组的数目 {
    public static void main(String[] args) {
        for (int i = 1; i < 1000; i++) {
            countLargestGroup(i);
        }
    }
    public static int countLargestGroup(int n) {
        int[] map = new int[37];
        int idx = 0;
        ok: for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    for (int v = 0; v < 10; v++) {
                        map[i+j+k+v]++;
                        if (++idx > n) {
                            break ok;
                        }
                    }
                }
            }
        }
        if (n == 10000) {
            map[1]++;
        }
        int count = 0, max=0;
        for (int i = 1; i < 37; i++) {
            int val = map[i];
            if (val == 0) {
                break;
            }
            if (val > max) {
                count=1;
                max = val;
            } else if (val == max) {
                count++;
            }
        }
        return count;
    }
}
